Data structures are important tools in the design of compilers, operating systems, algorithms and data bases. As used herein, the term data structure means a collection of data items, the relationships between the data items (e.g. the organization or arrangement of the data items) and the functions (operations) that can be applied to, or operate on, the data items. One simple example of a data structure is an integer array where the data items are integers, typically stored or arranged in an array of sequential memory locations and where the functions available include "store" (i.e. given a data item and a subscript, then associate that item with the subscript) and "retrieve" (i.e. given a subscript, provide the data item associated with the subscript).
Data structures are created and manipulated by programs executed on a computer and are stored in the computer's memory. The memory representation of a data structure is generally influenced by the hardware capabilities of the computer in which the structure will be used, and the efficiency of a particular data structure is directly influenced by the way in which the elements (items) of the structure are accessed by the memory hardware.
Although data structures may be implemented in a variety of hardware configurations, the performance of a given data structure can be quantified independent of hardware configuration, as long as a model of the computer is specified, e.g., a Random Access Machine (RAM) model. See, e.g., A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Programs, Addison-Welsey Pub. Co. Inc., Reading, Mass. (1974). Then, given a model, the performance of the given data structure can usually be quantified as a function of the number of data items in the data structure.
In the co-pending application, "Accessing Data Using Approximate Data Structures," Ser. No. 08/187,415, filed Jan. 24, 1994, by Yossi Matias, filed concurrently with this application, it was taught that it may be advantageous to approximate data structures by relaxing the operation, which define the data structure so that error of approximation in the results may be traded for speed in executing the operations.